package 左哥算法.ch05链表;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class Ch02复制带随机指针的链表 {

    /**
     * 题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
     * 请你复制该链表（深拷贝）
     */
    @Test
    public void test01(){
        int[] arr={1,2,2,1};
        Node head=new Node(arr[0]),curr;
        curr=head;
        for (int i=1;i<arr.length;i++) {
            curr.next=new Node(arr[i]);
            curr=curr.next;
        }
        Node copy1 = copyRandomList1(head);
        System.out.println(copy1);
        Node copy2 = copyRandomList2(head);
        System.out.println(copy2);
    }

    /**
     *  方法一:hash表方式，将链表的节点作为key，新节点作为value 放入hashMap中
     *      按链表顺序遍历hashMap，用原节点作为key，来获取新节点的next,和random
     */
    public Node copyRandomList1(Node head) {
        if (head==null) {
            return null;
        }
        Map<Node,Node> map=new HashMap<>();
        Node curr=head;
        while (curr != null) {  //复制新节点到map中
            map.put(curr,new Node(curr.val));
            curr=curr.next;
        }
        curr=head;
        while (curr != null) {
            Node fresh = map.get(curr);
            fresh.next=map.get(curr.next);
            fresh.random=map.get(curr.random);
            curr=curr.next;
        }
        return map.get(head);
    }

    /**
     * 方法二：先将新节点插入到老节点的后面，这样可以通过老节点来操作新节点
     * 如：a-a'-b-b'-c-c'
     *  这样新节点和老节点的关系为：fresh=old.next；fresh.random=old.random.next
     */
    public Node copyRandomList2(Node head) {
        if (head==null) {
            return null;
        }
        Node curr=head;
        while (curr!=null){     //将新节点插入到老节点后
            Node fresh = new Node(curr.val);
            fresh.next=curr.next;
            curr.next=fresh;
            curr=fresh.next;
        }
        curr=head;
        Node freshHead = curr.next; //保存新链表的头
        while (curr != null) {      //设置新节点的random
            Node fresh = curr.next;
            fresh.random=curr.random!=null?curr.random.next:null;
            curr=fresh.next;
        }
        curr=head;
        while (curr != null) {      //设置新节点的next以及恢复老节点的next
            Node fresh = curr.next;
            curr.next=fresh.next;
            fresh.next=fresh.next!=null?fresh.next.next:null;
            curr=curr.next;
        }
        return freshHead;
    }

    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
